import java.awt.*;
import java.util.*;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-07-17
 * Time: 22:44
 */

public class Solution {
    public int minReorder(int n, int[][] connections) {
        int result = 0;
        // 记录能到达的节点
        List<List<Integer>> lists1 = new ArrayList<>();
        // 记录到达它的节点
        List<List<Integer>> lists2 = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            List<Integer> list1 = new ArrayList<>();
            List<Integer> list2 = new ArrayList<>();
            lists1.add(list1);
            lists2.add(list2);
        }
        for (int i = 0; i < n - 1; i++) {
            int from = connections[i][0];
            int to = connections[i][1];
            lists1.get(from).add(to);
            lists2.get(to).add(from);
        }
        // 广度优先遍历
        // Set 里面储存的是已经遍历过的节点
        Set<Integer> set = new HashSet<>();
        set.add(0);
        // 队列里面存储的是每一次层的节点
        Queue<Integer> queue = new LinkedList<>();
        queue.add(0);
        while (!queue.isEmpty()) {
            // 得到 节点
            int node = queue.poll();
            // 先处理这个节点能到达的
            for (Integer to: lists1.get(node)) {
                if (!set.contains(to)) {
                    // 如果 to 不在 set 中, 那么就应该反向
                    result++;
                    // 并将新的节点加入到队列中
                    queue.add(to);
                    set.add(to);
                }
            }
            // 再处理能到达这个节点的, 这些都是不用变的
            for (Integer from: lists2.get(node)) {
                // 将新的节点加入到队列中
                queue.add(from);
                set.add(from);
            }

        }
        return result;
    }
}
